// @algorithm @lc id=100274 lang=cpp 
// @title fei-bo-na-qi-shu-lie-lcof

// @test(2)=1
// @test(5)=5
class Solution {
public:
    int fib(int n) {
        if(n<2) return n;
        int a=0, b=0, c=1;
        for(int i=2; i<=n; i++){
            a = b;
            b = c;
            c = (a+b)%1000'000'007;
        }
        return c;
    }
};